This book constitutes the proceedings of the 9th International Conference on Bio-inspired Computing: Theories and Applications, BIC-TA 2014, held in Wuhan, China, in October 2014. The 109 revised full papers presented were carefully reviewed and selected from 204 submissions. The papers focus on four main topics, namely evolutionary computing, neural computing, DNA computing, and membrane computing.

Membrane computing is an unconventional model of computation associated with a new computing paradigm. The field of membrane computing was initiated in 1998 by the author of this book; it is a branch of natural computing inspired by the structure and functioning of the living cell and devises distributed parallel computing models in the form of membrane systems. This book is the first monograph surveying the new field in a systematic and coherent way. It presents the central notions and results: the main classes of P systems, the main results about their computational power and efficiency, a complete bibliography, and a series of open problems and research topics.

Formal Languages and Applications provides a comprehensive study-aid and self-tutorial for graduates students and researchers. The main results and techniques are presented in an readily accessible manner and accompanied by many references and directions for further research. This carefully edited monograph is intended to be the gateway to formal language theory and its applications, so it is very useful as a review and reference source of information in formal language theory.

This book constitutes the thoroughly refereed post-conference proceedings of the 12th International Conference on Membrane Computing, CMC 2011, held in Fontainebleau, France, in August 2011. The 19 revised selected papers presented were carefully reviewed and selected from 27 papers and 5 posters presented at the conference. The book also contains full papers or extended abstracts of the 5 invited presentations. The papers address all the main directions of research in membrane computing, ranging from theoretical topics in the mathematics and computer science to application issues.

To our families The formal language theory was born in the middle of our century as a tool for modelling and investigating the syntax of natural languages, and it has been developed mainly in connection with programming language handling. Of course, one cannot deny the impulses from neuronal net investigations, from logic, as well as the mathematical motivation of the early researches. The theory has rapidly become a mature one, with specific problems, techniques and results and with an internal self-motivated life. Abstract enough to deal with the essence of modelled phenomena, formal language theory has been applied during the last years to many further non-linguistical fields, sometimes surprisingly far from the previous areas of applications; such fields are developmental biology, economic modelling, semiotics of folklore, dramatic and musical works, cryptography, sociology, psychology, and so on. All these applications as well as the traditional ones to natural and programming languages revealed a rather common conclusion: very frequently, context-free gram mars, the most developed and the most "tractable" type of Chomsky grammars, are not sufficient. "The world is non-context-free" (and we shall "prove" this statement in Section 0.4). On the other hand, the context-sensitive grammars are too powerful and definitely "intractable" (many problems are undecidable or are still open; there is no semantic interpretation of the nonterminals an so on). This is the reason to look for intermediate generative devices, conjoining the simpli city and the beauty of context-free grammars with the power of context-sensitive ones.

Dedicated to Arto Salomaa, a towering figure of theoretical computer science, on the occasion of his 65th birthday, this book is a tribute to him on behalf of the theoretical computer science community. The contributions are written by internationally recognized scientists and cover most of Salomaa's many research areas. Due to its representative selection of classic and cutting edge trends in theoretical computer science, the book constitutes a comprehensive state-of-the-art survey. The contributions are in such central areas as automata theory, algorithms and complexity, and combinatorics of words. But not only that, they take up new areas such as regular sets and biocomputing. While some are survey articles of fundamental topics, most are original research papers.

Marcus Contextual Grammars is the first monograph to present a class of grammars introduced about three decades ago, based on the fundamental linguistic phenomenon of strings-contexts interplay (selection). Most of the theoretical results obtained so far about the many variants of contextual grammars are presented with emphasis on classes of questions with relevance for applications in the study of natural language syntax: generative powers, descriptive and computational complexity, automata recognition, semilinearity, structure of the generated strings, ambiguity, regulated rewriting, etc. Constant comparison with families of languages in the Chomsky hierarchy is made. Connections with non-linguistic areas are established, such as molecular computing. Audience: Researchers and students in theoretical computer science (formal language theory and automata theory), computational linguistics, mathematical methods in linguistics, and linguists interested in formal models of syntax.

This is the first book on DNA computing, a molecular approach that may revolutionize computing-replacing silicon with carbon and microchips with DNA molecules. The book starts with an introduction to DNA computing, exploring the power of complementarity, the basics of biochemistry, and language and computation theory. It then brings the reader to the most advanced theories develop thus far in this emerging research area.

Membrane computing is a branch of natural computing which investigates computing models abstracted from the structure and functioning of living cells and from their interactions in tissues or higher-order biological structures. The models considered, called membrane systems (P systems), are parallel, distributed computing models, processing multisets of symbols in cell-like compartmental architectures. In many applications membrane systems have considerable advantages - among these are their inherently discrete nature, parallelism, transparency, scalability and nondeterminism.

In dedicated chapters, leading experts explain most of the applications of membrane computing reported so far, in biology, computer science, computer graphics and linguistics. The book also contains detailed reviews of the software tools used to simulate P systems.

This volume contains a selection of papers presented at the 10th Workshop on Membrane Computing, WMC 2009, which took place in Curtea de Arge, s, Romania, during August 24-27, 2009. The?rstthreeWorkshopsonMembraneComputingwereorganizedinCurtea de Arge, s, Romania - they took place in August 2000 (with the proceedings p- lished in Lecture Notes in Computer Science, volume 2235), in August 2001 (with a selection of papers published as a special issue ofFundamenta Inform- icae, volume 49, numbers 1-3, 2002), and in August 2002 (with the proceedings publishedinLectureNotesinComputerScience, volume2597).Thenextsixwo- shopswereorganizedinTarragona, Spain(inJuly2003), inMilan, Italy(inJune 2004), in Vienna, Austria (in July 2005), in Leiden, The Netherlands (in July 2006), in Thessaloniki, Greece (in June 2007), and in Edinburgh, UK (in July 2008), with the proceedings published as volumes 2933, 3365, 3850, 4361, 4860, and5391, respectively, ofSpringer'sLectureNotesinComputerScience. The workshop changed its name in 2010, and the series will continue as the Conference on Membrane Computing, with the next edition, CMC11, to be held in Jena, Germany. The tenth edition of WMC took place in Hotel Posada in Curtea de Arge, s (http: //www.posada.ro/)anditwasorganizedbytheNationalCollege"Vlaicu Voda" ? of Curtea de Arge, s, the University of Pite, sti, Romania, and the Institute of Mathematics of the Romanian Academy, Bucharest, under the auspices of the European Molecular Computing Consortium (EMCC) and IEEE Compu- tional Intelligence Society EmergentTechnologies Technical Committee Mole- lar Computing Task Force, with the ?nancial and organizational support of the Council of Arge, s County and Seville University."

This volume contains a selection of papers presented at the 9th Workshop on Membrane Computing, WMC9, which took place in Edinburgh, UK, during July 28-31,2008. The ?rst three workshopson membrane computing were or- nized in Curtea de Arge, s, Romania - they took place in August 2000 (with the proceedings published in Lecture Notes in Computer Science, volume 2235), in August 2001 (with a selection of papers published as a special issue of Fun- menta Informaticae, volume 49, numbers 1-3, 2002), and in August 2002 (with the proceedings published in Lecture Notes in Computer Science, volume 2597). The next ?ve workshops were organized in Tarragona, Spain, in July 2003, in Milan, Italy, in June 2004, in Vienna, Austria, in July 2005, in Leiden, The Netherlands, in July 2006, and in Thessaloniki, Greece, in June 2007, with the proceedings published as volumes 2933, 3365, 3850, 4361, and 4860 of Lecture Notes in Computer Science."

This book constitutes the thoroughly refereed extended postproceedings of the 8th International Workshop on Membrane Computing, WMC 2007, held in Thessaloniki, Greece, in June 2007 under the auspices of the European Molecular Computing Consortium (EMCC).

The 22 revised full papers presented together with 5 invited papers went through two rounds of reviewing and improvement. The papers in this volume cover all the main directions of research in membrane computing, ranging from theoretical topics in mathematics and computer science to application issues. A special attention was paid to the interaction of membrane computing with biology and computer science, focusing both on the biological roots of membrane computing, on applications of membrane computing in biology and medicine, and on possible electronically based implementations.

This book constitutes the refereed proceedings of the 5th International Conference on Unconventional Computation, UC 2006, held in York, UK, in September 2006. The 17 revised full papers presented together with four invited full papers were carefully reviewed and selected for inclusion in the book. All current aspects of unconventional computation are addressed - theory as well as experiments and applications.

The present volume is based on papers presented at the 6th Workshop on M- brane Computing, WMC6, which took place in Vienna, Austria, in the period July 18-21, 2005. The ?rst three workshops were organized in Curtea de Arge, s, Romania - they took place in August 2000 (with the proceedings published in Lecture Notes in Computer Science, volume 2235), in August 2001 (with a sel- tion of papers published as a special issue of Fundamenta Informaticae, volume 49, numbers 1-3, 2002), and in August 2002 (with the proceedings published in Lecture Notes in Computer Science, volume 2597). The fourth and the ?fth workshopswereorganizedinTarragona, Spain, in July2003, andin Milan, Italy, in June 2004, with the proceedings published as volumes 2933 and 3365, resp- tively, of Lecture Notes in Computer Science. The pre-proceedingsof WMC6 were published by the Institute for Computer Languages of the Vienna University of Technology, and they were available d- ing the workshop. Conforming with tradition, this workshop, too, was a lively scienti?c event, with many questions and engaged discussions following pres- tations of papers. Thecurrentvolumeisbasedonaselectionofpapersfromthepre-proceedings. These papers were signi?cantly modi?ed according to the discussions that took placeduringtheworkshop, andalltheselectedpaperswereadditionallyrefe

Membrane computing is a branch of natural computing which investigates computing models abstracted from the structure and functioning of living cells and from their interactions in tissues or higher-order biological structures. The models considered, called membrane systems (P systems), are parallel, distributed computing models, processing multisets of symbols in cell-like compartmental architectures. In many applications membrane systems have considerable advantages among these are their inherently discrete nature, parallelism, transparency, scalability and nondeterminism.

In dedicated chapters, leading experts explain most of the applications of membrane computing reported so far, in biology, computer science, computer graphics and linguistics. The book also contains detailed reviews of the software tools used to simulate P systems.

The Fourth International Conference on Unconventional Computation, UC 2005, organized under the auspices of EATCS by the Centre for Discrete Mathematics and Theoretical Computer Science and the Department of C- puter Science and Arti?cial Intelligence of the University of Seville, was held in Seville, October 3-7, 2005. Seville, one of the most beautiful cities in Spain, is at its best in October. An explosion of colour and contrast: ?amenco, bull?ghting, and a lively at- sphere in the streets due to the open and friendly nature of its people. The river Guadalquivir, the Cathedral and the Golden Tower are all places full of magic where the visitor can feel the spirit of a city which is eternally romantic. The series of International Conferences Unconventional Computation (UC), https: //www.cs.auckland.ac.nz/CDMTCS/conferences/uc/isdevoted to all aspects of unconventional computation, theory as well as experiments and applications. Typical, but not exclusive, topics are: natural computing including quantum, cellular, molecular, neural and evolutionarycomputing; chaosand - namical systems based computing; and various proposals for computations that go beyond the Turing model. The ?rst venue of the Unconventional Computation Conference (formerly called Unconventional Models of Computation) was Auckland, New Zealand in 1998; subsequent sites of the conference were Brussels, Belgium in 2000 and Kobe, Japan in 2002. The titles of the proceedings volumes from past UC Conferences are as follows: 1. C.S. Calude, J. Casti, M.J. Dinneen (eds.). Unconventional Models of C- putation, Springer-Verlag, Singapore, 1998, viii + 426 pp. ISBN: 981-3083- 69

This volume is based on papers presented at the5thWorkshoponM- brane Computing, WMC5, which took place in Milan, Italy, in the period June 14 16, 2004, as a satellite event of DNA10 (10th International Workshop on DNA-Based Computing). The ?rst three workshops were organized in Curtea de Arge, s, Romania they took place in August 2000 (with the proceedings p- lished in Lecture Notes in Computer Science, volume 2235), in August 2001 (with a selection of papers published as a special issue ofFundamenta Inform- icae, volume 49, numbers 1 3, 2002), and in August 2002 (with the proceedings publishedinLectureNotesinComputerScience, volume2597).Thefourthwo- shop took place in Tarragona, Spain, in July 2003 (the proceedings appeared as volume 2933 of Lecture Notes in Computer Science). Like the previous two meetings, also WMC5 was an o?cial workshop of the Molecular Computing Network (MolCoNet) funded by the EU Commission in theFifthFrameworkprogramInformationSocietyTechnologies(projectnumber IST-2001-32008). The preproceedings of WMC5 were published as a MolCoNet report, and they were available during the workshop. This volume contains only a selection of the papers from the preproceedings."

This is the first text and monograph about DNA computing, a molecular approach that might revolutionize our thinking and ideas about computing. Although it is too soon to predict whether computer hardware to change from silicon to carbon and from microchips to DNA molecules, the theoretical premises have already been studied extensively. The book starts with an introduction to DNA-related matters, the basics of biochemistry and language and computation theory, and progresses to the most advanced mathematical theory developed so far in the area. All three authors are pioneers in the theory of DNA computing. Apart from being well-known scientists, they are known for their lucid writing. Many of their previous books have become classics in their field, and this book too is sure to follow their example.

This Festschrift celebrates the 70th birthday of Arto Kustaa Salomaa (born in Turku, Finland on June 6, 1934), one of the most in?uential researchers in theoretical computer science. Most ofhis researchconcernstheory - he is one of the founding fathers of formal language and automata theory, but he has also made important contributions to cryptography and natural computing. His approach to research in theoretical computer science is exemplary and inspirational for his students, collaborators, andthereadersofhispapersandbooks. Forhim, theroleoftheory(incomputer science) is to discover general rules of information processing that hold within computer science and in the world around us. One should not waste time on research concerning passing artifacts (or fashionable topics of the moment) in computer science - theory should be permanently predictive, insightful, and inspiring. That's why we chose the title "Theory is Forever." The main source of his in?uence on theoretical computer science is his publi- tions. Arto is a born writer - his papers and books are always most elegant. He has a unique gift for identifying the real essence of a research problem, and then presenting it in an incisive and eloquent way. He can write about a very involved formal topic and yet avoid a (much too common) overformalization. Many of his writings are genuine jewels and belong to the classics of theoreticalcomputer science. Theyhaveinspiredgenerationsofstudentsandresearchers. Indeed, even computers as well as computer science have learned a lot from Arto's publi- tions - this is nicely illustrated by DADARA on the cover of this volume.

Formal Languages and Applications provides a comprehensive study-aid and self-tutorial for graduates students and researchers. The main results and techniques are presented in an readily accessible manner and accompanied by many references and directions for further research. This carefully edited monograph is intended to be the gateway to formal language theory and its applications, so it is very useful as a review and reference source of information in formal language theory.

This volume is based on papers presented at the Workshop on Membrane Computing, WMC 2003, which took place in Tarragona, Spain, in the - riod July 17-July 22, 2003. This was the Fourth Annual Membrane Computing Workshop, and the ?rst one held outside Romania. The ?rst three meetings were organized in Curtea de Arge, s, Romania - they took place in August 2000 (with the proceedings published in Lecture Notes in Computer Science, Vol. 2235), in August 2001 (with a selection of papers published as a special issue of F- damenta Informaticae, Vol. 49, Nos. 1-3, 2002), and in August 2002 (with the proceedings published in Lecture Notes in Computer Science, Vol. 2597). The 2003 workshop was the second workshop of the Molecular Computing Network (MolCoNet) funded by the EU Commission in the Fifth Framework Program Information Society Technologies (project number IST-2001-32008). The preproceedings of WMC 2003 were published as Technical Report 28/03 of theResearchGrouponMathematicalLinguisticsfromRoviraiVirgiliUniversity, Tarragona, and they were available during the workshop.

Molecular computing is a rapidly growing subarea of natural computing. On the one hand, molecular computing is concerned with the use of bio-molecules for the purpose of actual computations while, on the other hand, it attempts to understand the computational nature of molecular processes going on in living cells.

The book presents a unique and authorative state-of-the-art survey on current research in molecular computing: 30 papers by leading researchers in the area are drawn together on the occasion of the 70th birthday of Tom Head, a pioneer in molecular computing. Among the topics addressed are molecular tiling, DNA self-assembly, splicing systems, DNA-based cryptography, DNA word design, gene assembly, and membrane computing.

This book constitutes the thoroughly refereed post-proceedings of the International Workshop on Membrane Computing, WMC-CdeA 2002, held in Curtea de Arges, Romania, in August 2002. The 29 revised full papers presented were carefully selected during two rounds of reviewing and revision; some were especially solicited for inclusion in the book after the workshop. Most papers address membrane systems and membrane computing from the point of view of theoretical computer science; some papers solve open problems and present new approaches, and others provide mathematical and biological background. All in all, the book presents the state of the art in membrane computing.

The multiset, as a set with multiplicities associated with its elements in the form of natural numbers, is a notation which has appeared again and again in various areas of mathematics and computer science. As a data structure, multisets stand in-between strings/lists, where a linear ordering of symbols/items is present, and sets, where no ordering and no multiplicity is considered. This book presents a selection of thoroughly reviewed revised full papers contributed to a workshop on multisets held in Curtea de Arges, Romania in August 2000 together with especially commissioned papers. All in all, the book assesses the state of the art of the notion of multisets, the mathematical background, and the computer science and molecular computing relevance.

The finite - infinite interplay is central in human thinking, from ancient philosophers and mathematicians (Zeno, Pythagoras), to modern mathe matics (Cantor, Hilbert) and computer science (Turing, Godel). Recent developments in mathematics and computer science suggest a) radically new answers to classical questions (e. g. , does infinity exist?, where does infinity come from?, how to reconcile the finiteness of the human brain with the infinity of ideas it produces?), b) new questions of debate (e. g. , what is the role played by randomness?, are computers capable of handling the infinity through unconventional media of computation?, how can one approximate efficiently the finite by the infinite and, conversely, the infinite by finite?). Distinguished authors from around the world, many of them architects of the mathematics and computer science for the new century, contribute to the volume. Papers are as varied as Professor Marcus' activity, to whom this volume is dedicated. They range from real analysis to DNA com puting, from linguistics to logic, from combinatorics on words to symbolic dynamics, from automata theory to geography, and so on, plus an incursion into the old history of conceptions about infinity and a list of philosophical "open problems". They are mainly mathematical and theoretical computer science texts, but not all of them are purely mathematical.